\section{Omitted Proofs of Section~\ref{sec:lowerbound} (Lower Bound)}

\subsection{Proof of Lemma~\ref{lem:one}}
\label{proof:lem:one}
\begin{proof}
After the first $k$ free rounds, consider the intervals that the
left subtree can have, in the best case. Recall that these $k$
rounds allowed communication only along the path. The $path\_dist$
of any node in $L$ from the breakpoints of $sub(L)$ along the path
is at least $k+1$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Proof of Lemma~\ref{lem:two}}
\label{proof:lem:two}
\begin{proof}
First, notice that each left breakpoint is at a path-distance of
$k+1$ from every node in the right subtree. That is,
$path\_dist(u,L) = path\_dist(v,R) = k+1$ for all $u\in B_l$ and all
$v\in B_r$.

%{\bf Gopal:} Explain "connected" below.

%{\bf Danupon:} The sentence is changed.

Each breakpoint needs to be combined into one interval in the end.
However, there could be one interval that is communicated from the
$sub(l)$ to the $sub(r)$ (or vice versa) such that it connects
several breakpoints. We show that this cannot happen. Consider all
the breakpoints $v\in B_l\cup B_r$.

\noindent{\bf Definition of {\em scratching}}.

Let us say that we {\em scratch out} the breakpoints from the list
$k+1$, $k'/2+k+1$, $k'+k+1$, $k'+k'/2+k+1$, $2k'+k+1$, ... that get
connected when an interval is communicated between $sub(l)$ and
$sub(r)$. We scratch out a breakpoint if there is an interval in the
graph that contains it and both (or one in case of the first and
last breakpoints) its adjacent breakpoints. For example, if the left
subtree has intervals $[1, k'/2+k]$ and $[k'/2+k+2, k'+k'/2+k+1]$
and the right subtree has $[k+2, k'+k]$ and the latter interval is
communicated to a node in the left subtree, then the left subtree is
able to obtain the merged interval $[1,k'+k'/2+k+1]$ and therefore
breakpoints $k+1$ and $k'/2+k+1$ are scratched out.

\begin{claim}
\label{claim:one} At most $O(1)$ breakpoints can be scratched out
with one message/interval communicated between $sub(r)$ and $sub(l)$
\end{claim}
\begin{proof}
We argue that with the communication of one interval across the left
and right subtrees, at most $4$ breakpoints that have not been
scratched yet can get scratched. This follows from a simple
inductive argument. Consider a situation where the left subtree has
certain intervals with all overlapping intervals already merged, and
similarly right subtree. Suppose an interval ${\cal I}$ is
communicated between $sub(r)$ and $sub(l)$, one of the following
cases arise:
%\begin{itemize}
\squishlist
\item ${\cal I}$ contains one breakpoint: Can be merged with at most two other intervals. Therefore, at most three breakpoints can get scratched.
\item ${\cal I}$ contains two breakpoints: Can get connected with at most two other intervals and therefore at most four breakpoints can get scratched.
\item ${\cal I}$ contains more than two breakpoints: This is impossible since there are at most two breakpoints in each interval, its left most and
right most numbers (by definition of scratching).
%The important point is that ${\cal I}$ can contain at most two breakpoints that have not been scratched yet (by definition).
%\end{itemize}
\squishend This completes the proof of the claim.
\end{proof}

%{\bf Gopal:} Better to say that "the last case does not arise because ...."

%{\bf Danupon:} The sentence of the last case is changed. See above.

The proof now follows from Lemma~\ref{lem:one}. For any breakpoint
$b$, let $M_b$ be the set of messages that represents an interval
containing $b$ while $b$ is still unscratched. If $b$ is in $sub(l)$
and gets scratched because of the combination of some intervals in
$sub(r)$, then we claim that $M_b$ has covered a path-distance of at
least $k$. (Define the path-distance covered by $M_b$ by the total
path-distance covered by all messages in $M_b$.) This is because $b
= v_i$ (say), being a breakpoint in $sub(l)$ has $i$ equal to $(k+1
\mod k')$. Therefore, $b$ is at a path distance of at least $k$ from
any node in $R$. Consequently, $b$ is at a path-distance of at least
$k$ from any node in $sub(r)$. Since there are
$\Theta(\frac{n}{4k})$ breakpoints, and for any interval to be
communicated across the left and right subtree, a path-distance of
$k$ must be covered, in total, $\Theta(n)$ path-distance must be
covered for all breakpoints to be scratched. This follows from three
main observations:
%\begin{itemize}
\squishlist
\item As shown above, for any breakpoint to be scratched, an interval with a breakpoint must
be communicated from $sub(l)$ to $sub(r)$ or vice versa (thereby all
messages $m$ containing the breakpoint together covering a
path-distance of at least $k$)
\item Any message/interval with unscratched breakpoints has at most two unscratched breakpoints
\item As shown in Claim~\ref{claim:one}, at most four breakpoints can be scratched when two intervals are merged.
\squishend
%\end{itemize}

The proof follows. (Also see Figure~\ref{fig:scratch_4} for the idea of this proof.)
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\iffalse
\subsection{Proof of Lemma~\ref{lem:three}}
\label{proof:lem:three}
\begin{proof}
We consider the total number of messages that can go through nodes
at any level of the graph, starting from level $0$ to level $\log k$
under the congest model.

First notice that if a message is passed at level $i$ of the tree,
this can cover a $path\_dist$ of at most $2^i$. This is because the
subtree rooted at a node at level $i$ has $2^i$ leaves. Further, by
our construction, there are $2^{\log (k') - i}$ nodes at level $i$.
Therefore, all nodes at level $i$ together, in a given round of
$\mathcal A$ can cover a $dist-path$, path distance, of at most
$2^i2^{\log (k') - i} = 4k+2$. Therefore, over $k$ rounds, the total
$path\_dist$ that can be covered in a single level is $k(k')$. Since
there are $O(\log k)$ levels, the total $path\_dist$ that can be
covered in $k$ rounds over the entire graph is $O(k^2\log k)$. (See
Figure~\ref{fig:max_path_cover}.)
\end{proof}
%\fi






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%\textbf{Danupon:} The problem with the above proof is that the weights are really huge. So, we cannot call them multiple edge.
%One idea to fix this is to put only $2^i$ edges between $v_i$ and $v_{i+1}$ and argue that the walk will have length $\Omega(n)$ with
%high probability. Then, we need to modify the theorem to deal with paths of length, say $n/2$, as well. Is $2^n$ small enough?
%
%{\bf Gopal:} Why we cannot call them multiple edge (as I say in the proof above)? What is the differnece
%if the wieght is $2^i$ as opposed to $n^i$ ?
%{\bf Danupon:} My only worry is that $n^i$ is too much for the number of edges. (That's also true for $2^i$.)
%If you think it is fine then that is ok.
%
%Another idea is to only show that with constant probability that the path will be taken.
%Then our lower bound statement will hold with constant probability instead of high probablity.
%In this case, we need only polynomial weights -- $n^2$ will suffice for every edge in the path. Do you agree?
%If this is correct, we can state this also.

\section{Omitted Proofs of Section~\ref{sec:mixingtime} (Mixing Time)}

\subsection{Brief description of algorithm for Theorem~\ref{thm:batu}}\label{app:batu}

The algorithm partitions the set of nodes in to buckets based on the steady state probabilities. Each of the $\tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ samples from $X$ now falls in one of these buckets. Further, the actual count of number of nodes in these buckets for distribution $Y$ are counted. The exact count for $Y$ for at most $\tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ buckets (corresponding to the samples) is compared with the number of samples from $X$; these are compared to determine if $X$ and $Y$ are close. We refer the reader to their paper~\cite{BFFKRW} for a precise description.

\subsection{Proof of Lemma~\ref{lem:monotonicity}}\label{app:mon}
\begin{proof}
The monotonicity follows from the fact that
$||Ax||_1 \le ||x||_1$ where $A$ is the transpose of the transition probability matrix of the graph and $x$ is any probability vector. That is, $A(i,j)$ denotes the probability of transitioning from node $j$ to node $i$. This in turn follows from the fact that the sum of entries of any column of $A$ is 1.

Now let $\pi$ be the stationary distribution of the transition matrix $A$. This implies that if $\ell$ is $\epsilon$-near mixing, then $||A^lu - \pi||_1 \leq \epsilon$, by definition of $\epsilon$-near mixing time. Now consider $||A^{l+1}u - \pi||_1$. This is equal to $||A^{l+1}u - A\pi||_1$ since $A\pi = \pi$.  However, this reduces to $||A(A^{l}u - \pi)||_1 \leq \epsilon$. It follows that $(\ell+1)$ is $\epsilon$-near mixing.
\end{proof}
%\Closesolutionfile{movedProofs}

\subsection{Proof of Theorem~\ref{thm:mixmain}}\label{app:mixproof}
\begin{proof}
For undirected unweighted graphs, the
stationary distribution of the random walk is known and is
$\frac{deg(i)}{2m}$ for node $i$ with degree $deg(i)$, where $m$ is
the number of edges in the graph.  If a source node in the network knows the degree distribution, we only need
$\tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ samples from a distribution to
compare it to the stationary distribution.  This can be achieved by
running {\sc MultipleRandomWalk} to obtain $K = \tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ random walks. We choose $\epsilon = 1/12e$.
To find the approximate mixing time, we try out
increasing values of $l$ that are powers of $2$.  Once we find the
right consecutive powers of $2$, the monotonicity property admits a
binary search to determine the exact value for the specified $\epsilon$.
%of $\epsilon$-near mixing
%time. Note that we can apply binary search as $\epsilon$-near mixing
%time is a monotonic property.

The result
in~\cite{BFFKRW} can also be adapted to compare with the steady state distribution even if the source does not know the entire distribution. As described previously, the source only needs to know the {\em count} of number of nodes with steady state distribution in given buckets. Specifically, the buckets of interest are at most $\tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ as the count is required only for buckets were a sample is drawn from. Since each node knows its own steady state probability (determined just by its degree), the source can broadcast a specific bucket information and recover, in $O(D)$ steps, the count of number of nodes that fall into this bucket. Using the standard upcast technique previously described, the source can obtain the bucket count for each of these at most $\tilde{O}(n^{1/2}poly(\epsilon^{-1}))$ buckets in $\tilde{O}(n^{1/2}poly(\epsilon^{-1}) + D)$ rounds.


We have shown previously that a source node can obtain $K$ samples from $K$ independent random walks of length $\ell$ in $\tilde{O}(K + \sqrt{KlD})$ rounds. Setting $K=\tilde{O}(n^{1/2}poly(\epsilon^{-1}) + D)$ completes the proof.
\end{proof}

\section{Figures}


\begin{figure}[h]
\centering
\includegraphics{path_verify_definition.pdf}
\caption{Example of path verification problem. {\bf (a)} In the
beginning, we want to verify that the vertices containing numbers
$1..5$ form a path. (In this case, they form a path $a, b, c, d,
a$.) {\bf (b)} One way to do this is for $a$ to send $1$ to $b$ and
therefore $b$ can check that two vertices $a$ and $b$ corresponds to
label $1$ and $2$ form a path. (The interval $[1,2]$ is used to
represent the fact that vertices corresponding to numbers $1, 2$ are
verified to form a path.) Similarly, $c$ can verify $[3,5]$. {\bf
(c)} Finally, $c$ combine $[1,2]$ with $[3, 5]$ and thus the path
corresponds to numbers $1,2, ..., 5$ is verified. }
\label{fig:path_verify_definition}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=0.98\linewidth]{connector-2.pdf}
\caption{Figure illustrating the Algorithm of stitching short walks together.}
\label{fig:connector}
\end{figure}

\begin{figure}[h]
  \centering
  \includegraphics[width=0.7\linewidth]{Graph_Construction.pdf}\\
  \caption{$G_n$}\label{fig:graph_construction}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics{breaking-points.pdf}
\caption{\textbf{Breakpoints.} {\bf (a)} $L$ and $R$ consist of
every other $k'/2$ vertices in $P$. (Note that we show the vertices
$l$ and $r$ appear many times for the convenience of presentation.)
{\bf (b)} $v_{k'/2+k+1}$ and $v_{k'+k'/2+k+1}$ (nodes in black) are
two of the breakpoints for $L$. Notice that there is one breakpoint
in every connected piece of $L$ and $R$.}
\label{fig:breaking-points}
\end{figure}

\begin{figure}[h]
\centering \subfigure[{Path-distance.}]{
\includegraphics[width=0.35\linewidth]{path-distance.pdf}
\label{fig:path_distance}}
%
\subfigure[{Idea of Claim~\ref{claim:one}}]{
\includegraphics[width=0.35\linewidth]{scratch_4.pdf}
\label{fig:scratch_4} }
%
\subfigure[Idea of Lemma~\ref{lem:three}.]{
\includegraphics[width=0.25\linewidth]{max_path_cover.pdf}
\label{fig:max_path_cover} } \caption{{\bf (a)} Path distance
between 1 and 2 is the number of leaves in the subtree rooted at 3,
the lowest common ancestor of 1 and 2. {\bf (b)} For one unscratched
left breakpoint, $k'/2+k+1$ to be combined with another right
breakpoint $k+1$ on the left, $k'/2+k+1$ has to be carried to $L$ by
some intervals. Moreover, one interval can carry at most two
unscratched breakpoints at a time. {\bf (c)} Sending a message
between nodes on level $i$ and $i-1$ can increase the covered path
distance by at most $2^i$.}
\end{figure}
ther.}
\label{fig:connector}
\end{figure}

\begin{figure}[h]
  \centering
  \includegraphics[width=0.7\linewidth]{Graph_Construction.pdf}\\
  \caption{$G_n$}\label{fig:graph_construction}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics{breaking-points.pdf}
\caption{\textbf{Breakpoints.} {\bf (a)} $L$ and $R$ consist of
every other $k'/2$ vertices in $P$. (Note that we show the vertices
$l$ and $r$ appear many times for the convenience of presentation.)
{\bf (b)} $v_{k'/2+k+1}$ and $v_{k'+k'/2+k+1}$ (nodes in black) are
two of the breakpoints for $L$. Notice that there is one breakpoint
in every connected piece of $L$ and $R$.}
\label{fig:breaking-points}
\end{figure}

\begin{figure}[h]
\centering \subfigure[{Path-distance.}]{
\includegraphics[width=0.35\linewidth]{path-distance.pdf}
\label{fig:path_distance}}
%
\subfigure[{Idea of Claim~\ref{claim:one}}]{
\includegraphics[width=0.35\linewidth]{scratch_4.pdf}
\label{fig:scratch_4} }
%
\subfigure[Idea of Lemma~\ref{lem:three}.]{
\includegraphics[width=0.25\linewidth]{max_path_cover.pdf}
\label{fig:max_path_cover} } \caption{{\bf (a)} Path distance
between 1 and 2 is the number of leaves in the subtree rooted at 3,
the lowest common ancestor of 1 and 2. {\bf (b)} For one unscratched
left breakpoint, $k'/2+k+1$ to be combined with another right
breakpoint $k+1$ on the left, $k'/2+k+1$ has to be carried to $L$ by
some intervals. Moreover, one interval can carry at most two
unscratched breakpoints at a time. {\bf (c)} Sending a message
between nodes on level $i$ and $i-1$ can increase the covered path
distance by at most $2^i$.}
\end{figure}
